package com.hc.programming.stack;

import java.util.Stack;

/**
 * 给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
 * 有效字符串需满足：
 * 1.左括号必须用相同类型的右括号闭合。
 * 2.左括号必须以正确的顺序闭合。
 * 3.每个右括号都有一个对应的相同类型的左括号。
 * <p>
 * 示例 1：
 * 输入：s = "()"
 * 输出：true
 * 示例 2：
 * 输入：s = "()[]{}"
 * 输出：true
 * 示例 3：
 * 输入：s = "(]"
 * 输出：false
 * 示例 4：
 * 输入：s = "([])"
 * 输出：true
 * <p>
 * 提示：
 * 1 <= s.length <= 10^4
 * s 仅由括号 '()[]{}' 组成
 *
 * @author huangchao E-mail:fengquan8866@163.com
 * @version 创建时间：2024/10/31 15:47
 */
public class 有效的括号 {
    public static void main(String[] args) {
        System.out.println(isValid("()") + "========true");
        System.out.println(isValid("()[]{}") + "========true");
        System.out.println(isValid("(]") + "========false");
        System.out.println(isValid("([])") + "========true");
    }

    public static boolean isValid(String s) {
//        return 元素入栈(s);
//        return 反括号入栈(s);
        return 数组存储(s);
    }

    private static boolean 数组存储(String s) {
        if (s.length() % 2 != 0) return false;
        char[] arr = new char[s.length()];
        int p = -1;
        for (char c : s.toCharArray()) {
            if (c == '(') {
                arr[++p] = ')';
            } else if (c == '[') {
                arr[++p] = ']';
            } else if (c == '{') {
                arr[++p] = '}';
            } else if (p == -1 || arr[p] != c) {
                return false;
            } else {
                p--;
            }
        }
        return p == -1;
    }

    private static boolean 反括号入栈(String s) {
        if (s.length() % 2 != 0) return false;
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(') {
                stack.push(')');
            } else if (c == '[') {
                stack.push(']');
            } else if (c == '{') {
                stack.push('}');
            } else if (stack.isEmpty() || stack.pop() != c) {
                return false;
            }
        }
        return stack.isEmpty();
    }

    private static boolean 元素入栈(String s) {
        if (s.length() % 2 != 0) return false;
        Stack<Character> stack = new Stack<>();
        for (char c : s.toCharArray()) {
            if (c == '(' || c == '[' || c == '{') {
                stack.push(c);
            } else {
                if (stack.isEmpty()) return false;
                Character pop = stack.pop();
                if (c == ')' && pop != '(') return false;
                if (c == ']' && pop != '[') return false;
                if (c == '}' && pop != '{') return false;
            }
        }
        return stack.isEmpty();
    }
}
